package com.mgq.algorithm.twotree;

import java.util.*;

import static com.mgq.algorithm.twotree.SerializeTree.deserializeTree;
import static com.mgq.algorithm.twotree.SerializeTree.serializeTree;

/**
 * 遍历二叉树
 */
public class TraversalTree {
    /**
     * 递归序.每个节点都会被访问3次
     * @param node
     */
    public static void f(TreeNode node) {
        //B 1.
        if (node==null) return;
        //E 1.
        System.out.println(node);
        f(node.left);
        //B 2.
        //E 2.
        System.out.println(node);
        f(node.right);
        System.out.println(node);
        //B 3.
        //E 3.
    }

    /**
     * 先序遍历, 递归序第一次访问的时候打印
     * @param node
     */
    public static void pre(TreeNode node) {
        //1.
        if (node==null) return;
        System.out.println(node);
        //1.
        pre(node.left);
        pre(node.right);
    }

    /**
     * 先序遍历,使用非递归形式
     * 采用压栈的方式
     * 栈里面内容
     * 弹出 1 打印
     * 3,2 栈里面(3,2)
     * 弹出 2 打印 栈里面(3,5,4)
     * 弹出 4 打印 栈里面(3,5)
     * 弹出 5 打印 栈里面(3)
     * 弹出 3 打印  7,6 压入栈里面(7,6)
     * 弹出6 打印6  栈里面(7)
     * 弹出7 打印7
     * @param node
     */
    public static void preStack(TreeNode node) {
        Stack<TreeNode> stack = new Stack<>();
        stack.push(node);
        while (!stack.isEmpty()) {
            TreeNode root = stack.pop();
            System.out.println(root);
            if (root.right != null) {
                stack.push(root.right);
            }
            if (root.left != null) {
                stack.push(root.left);
            }
        }
    }
    /**
     * 中序遍历, 递归序第二次访问的时候打印
     * @param node
     */
    public static void mid(TreeNode node) {
        if (node==null) return;
        mid(node.left);
        //2.
        System.out.println(node);
        //
        mid(node.right);
    }
    /**
     * 中序遍历 非递归
     * 先将左子树压入栈,依次弹出打印,将指针移动到右子树,继续
     *
     * 实质是: 一棵树可以根据左子树来全部划分开.
     * 我们每次压入左子树,就相当于弹出是左,根 (打印)
     * 又因为指针移动到右子树,然后右子树又可以分为左根 右
     * 即 (每一个右都可以划分为左根右),我们依次走完时,就按照左根右的顺序进行了遍历
     * 左 根 右
     *       左 根  右
     *              左 根  右
     * @param node
     */
    public static void midStack(TreeNode node) {
        Stack<TreeNode> stack = new Stack<>();
        if (node != null) {
            while (node != null||!stack.isEmpty()) {
                //这个if是不断的把左节点全部压入栈
                if (node != null) {
                    stack.push(node);
                    node = node.left;
                } else {
                    node = stack.pop();
                    System.out.println(node);
                    //指针到右边,继续
                    node = node.right;
                }
            }
        }

    }
    /**
     * 后序遍历, 递归序第三次访问的时候打印
     * @param node
     */
    public static void post(TreeNode node) {
        if (node==null) return;
        post(node.left);
        post(node.right);
        //3.
        System.out.println(node);
    }


    /**
     * 后序遍历,采用非递归形式
     * 准备2个栈,一个作为辅助栈
     * 我们只要第一个栈的出栈顺序是 根 右 左时, 再压入第二个辅助栈,我们第二个辅助栈出栈就是左右根,也就是后续遍历的方式
     * @param node
     */
    public static void postStack(TreeNode node) {
        Stack<TreeNode> s1 = new Stack<>();
        Stack<TreeNode> s2 = new Stack<>();
        s1.push(node);
        while (!s1.isEmpty()) {
            TreeNode tree = s1.pop();
            s2.push(tree);
            if (tree.left != null) {
                s1.push(tree.left);
            }
            if (tree.right != null) {
                s1.push(tree.right);
            }
        }

        while (!s2.isEmpty()) {
            System.out.println(s2.pop());
        }
    }

    /**
     * 宽度优先遍历 (就相当于一层一层的遍历)
     * 1,2,3,4,5,6,7
     *                 1
     *               /  \
     *              2    3
     *             / \  / \
     *            4  5 6  7
     *
     * @param node
     */
    public static void width(TreeNode node) {
        if (node==null) return;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(node);
        while (!queue.isEmpty()) {
            TreeNode cur = queue.poll();
            System.out.println(cur);
            if (cur.left != null) {
                queue.add(cur.left);
            }
            if (cur.right != null) {
                queue.add(cur.right);
            }
        }
    }

    /**
     * 获取二叉树的最大宽度
     *                 1
     *               /  \
     *              2    3
     *             / \  / \
     *            4  5 6  7
     *  最大宽度是4
     *                 1
     *               /  \
     *              2    3
     *             / \  /
     *            4  5 6
     *    最大宽度是3
     *    思路,需要每次记录所在的层级,同时还要记录层级的节点个数
     * @param node
     */
    public static int getWidth(TreeNode node) {
        if (node==null) return 0;
        //表示当前遍历所在的层数
        Integer curLevel=1;
        //当前节点的个数
        Integer curNodeCount=0;
        //最大的个数
        Integer max=-1;
        //保存的是node所在的层数
        HashMap<TreeNode, Integer> levelMap = new HashMap<>();
        levelMap.put(node, 1);
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(node);
        while (!queue.isEmpty()) {
            TreeNode cur = queue.poll();
            //当前node所在的层数
            Integer curNodeLevel = levelMap.get(cur);
            if (Objects.equals(curNodeLevel, curLevel)) {
                curNodeCount++;
            }else {
                max = Math.max(max, curNodeCount);
                curLevel++;
                //到这的时候,说明已经是下一层了,已经有一个节点了
                curNodeCount=1;
            }
            if (cur.left != null) {
                //下一层
                levelMap.put(cur.left, curNodeLevel+1);
                queue.add(cur.left);
            }
            if (cur.right != null) {
                levelMap.put(cur.right, curNodeLevel+1);
                queue.add(cur.right);
            }
        }
        //需要考虑最后一层的情况
        //最后比较最后一层的大小
        max = Math.max(max, curNodeCount);
        return max;
    }



    public static void main(String[] args) {
        TreeNode node1 = new TreeNode(1);
        TreeNode node2 = new TreeNode(2);
        TreeNode node3 = new TreeNode(3);
        TreeNode node4 = new TreeNode(4);
        TreeNode node5 = new TreeNode(5);
        TreeNode node6 = new TreeNode(6);
        TreeNode node7 = new TreeNode(7);
        TreeNode node8 = new TreeNode(8);
        TreeNode node9 = new TreeNode(9);
        node1.left=node2;
        node1.right=node3;
        node2.left=node4;
        node2.right=node5;
        node3.left=node6;
        node3.right=node7;

       // node5.left=node8;
        // node5.right=node9;
        //递归序
       // f(node1);
       // pre(node1);
        //preStack(node1);
        //mid(node1);
        //midStack(node1);
       // post(node1);
        //postStack(node1);
        //width(node1);
       // int width = getWidth(node1);
        //System.out.println(width);
        String s = serializeTree(node1);
        TreeNode node = deserializeTree(s);
        pre(node);
    }
}
